// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-05 14:48
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain.UFS;

import org.junit.jupiter.api.Test;

@SuppressWarnings("ALL")
public class FindCircleNumByDFS {
    /**
     * 使用深度优先遍历计算给定图中联通图的数量
     */
    int[] Path;

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        // 保存节点是否被访问过的信息
        Path = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (Path[i] == 0) {
                DFS(i, isConnected);
                ++ans;
            }
        }
        return ans;
    }

    private void DFS(int k, int[][] isConnected) {
        // 使用DFS遍历图中的节点-> 踩点
        Path[k] = 1;
        int n = isConnected.length;
        if (k > n) {
            return;
        }
        int m = isConnected[0].length;
        for (int j = 0; j < m; j++) {
            if (isConnected[k][j] == 1 && Path[j] == 0) {
                // 当前的两个节点存在路径
                Path[j] = 1;
                DFS(j, isConnected);
            }
        }
    }

    @Test
    public void shout() {
        int[][] isConnected = {{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 1}};
        System.out.println(findCircleNum(isConnected));
    }
}
